package struct;

import java.util.PriorityQueue;

/**
 * 只进不出数据流的中位数
 *      将数据按照中间值分为两半
 */
public class MedianFinder {

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();

        medianFinder.addNum(1, 2, 5, 6, 7, 8);
        System.out.println(medianFinder.findMedian());

    }

    private final PriorityQueue<Integer> MAX_HEAP = new PriorityQueue<>((a, b) -> b - a);
    private final PriorityQueue<Integer> MIN_HEAP = new PriorityQueue<>();

    public MedianFinder() {
    }

    public void addNum(int num) {
        // 优先进大根堆
        if (MAX_HEAP.isEmpty() || MAX_HEAP.peek() > num) {
            MAX_HEAP.add(num);
        } else {
            MIN_HEAP.add(num);
        }

        balance();
    }

    public void addNum(int... nums) {
        for (int num : nums) {
            addNum(num);
        }
    }

    private void balance() {
        if (Math.abs(MAX_HEAP.size() - MIN_HEAP.size()) <= 1) {
            return;
        }

        if (MAX_HEAP.size() > MIN_HEAP.size()) {
            MIN_HEAP.add(MAX_HEAP.poll());
        } else {
            MAX_HEAP.add(MIN_HEAP.poll());
        }

    }

    public double findMedian() {
        if (MIN_HEAP.isEmpty() && MAX_HEAP.isEmpty()) {
            return -1;
        }

        if ((MIN_HEAP.size() + MAX_HEAP.size() & 1) == 1) {
            return (double) MIN_HEAP.size() > MAX_HEAP.size() ? MIN_HEAP.peek() : MAX_HEAP.peek();
        }

        return (MAX_HEAP.peek() + MIN_HEAP.peek()) / 2.0;
    }

}
